/**
 * @param {number[][]} grid
 * @return {number}
 */
export var countNegatives = function (grid) {
  let ans = 0
  const [m, n] = [grid.length, grid[0].length]
  let preRight = n - 1
  for (let i = 0; i < m; i++) {
    const right = bisect(grid[i], preRight)
    if (right > -1) {
      ans += n - right
      preRight = right
    }
  }
  return ans
}

function bisect(arr, right) {
  let left = 0
  right = right || arr.length - 1
  let ans = -1
  while (left <= right) {
    const mid = (left + right) >> 1
    if (arr[mid] < 0) {
      ans = mid
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  return ans
}
